package com.le.high.class5;

import org.junit.Test;

/**
 * 给定一个正数1，裂开的方法有一种，(1)
 * 给定一个正数2，裂开的方法有两种，(1和1)、(2)
 * 给定一个正数3，裂开的方法有三种，(1、1、1)、(1、2)、(3)
 * 给定一个正数4，裂开的方法有五种，(1、1、1、1)、(1、1、2)、(1、3)、（2、2）,（4）
 * 给定一个正数n，求裂开的方法数。
 */
public class Problem02_SplitNumber {
    public static int getNumber(int n) {
        if (n < 2) {
            return n < 1 ? 0 : n;
        }
        return process(1, n);
    }

    /**
     * @param pre  当前分配数字必须必前边大
     * @param rest n 剩余数量
     * @return 方法数
     */
    public static int process(int pre, int rest) {
        if (rest == 0) {
            return 1;
        }
        if (pre > rest) {
            return 0;
        }
        int res = 0;
        for (int i = pre; i <= rest; i++) {
            res += process(i, rest - i);
        }
        return res;
    }

    public static int getNumber1(int n) {
        if (n <= 0) {
            return 0;
        }
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
            dp[i][i] = 1;
        }
        for (int pre = n - 1; pre > 0; pre--) {
            for (int rest = pre + 1; rest <= n; rest++) {
                for (int i = pre; i <= rest; i++) { // 枚举行为
                    dp[pre][rest] += dp[i][rest - i];
                }
            }
        }
        return dp[1][n];

    }

    public static int getNumber2(int n) {
        if (n <= 0) {
            return 0;
        }
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
            dp[i][i] = 1;
        }
        for (int pre = n - 1; pre > 0; pre--) {
            for (int rest = pre + 1; rest <= n; rest++) {
                dp[pre][rest] = dp[pre + 1][rest] + dp[pre][rest - pre];
            }
        }
        return dp[1][n];

    }

    @Test
    public void test() {
        for (int i = 0; i < 10; i++) {
            System.out.println((i + 1) + ":" + getNumber(i + 1) + "-->" + getNumber1(i + 1)+ "-->" + getNumber2(i + 1));
        }
    }
}
